package main.leetcode.primary.from201to300;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 *
 * <p>设计一个支持以下两种操作的数据结构：
 *
 * <p>void addWord(word) bool search(word) search(word) 可以搜索文字或正则表达式字符串，字符串只包含字母 . 或 a-z 。 .
 * 可以表示任何一个字母。
 *
 * <p>示例: addWord("bad") <br>
 * addWord("dad") <br>
 * addWord("mad") <br>
 * search("pad") -> false <br>
 * search("bad") -> true <br>
 * search(".ad") -> true <br>
 * search("b..") -> true
 *
 * <p>说明: 你可以假设所有单词都是由小写字母 a-z 组成的。
 */
public class ex211 {
    public static void main(String[] args) {
        WordDictionary root = new WordDictionary();
        root.addWord("bad");
        root.addWord("dad");
        root.addWord("mad");
        System.out.println(root.search("pad"));
        System.out.println(root.search("bad"));
        System.out.println(root.search(".ad"));
        System.out.println(root.search("b.."));
    }

    static class WordDictionary {
        private WordDictionary[] next;
        private boolean isEnd;

        /** Initialize your data structure here. */
        public WordDictionary() {
            next = new WordDictionary[26];
            isEnd = false;
        }

        /** Adds a word into the data structure. */
        public void addWord(String word) {
            WordDictionary cur = this;
            char[] chars = word.toCharArray();
            for (char c : chars) {
                int pos = c - 'a';
                if (cur.next[pos] == null) {
                    cur.next[pos] = new WordDictionary();
                }
                cur = cur.next[pos];
            }
            cur.isEnd = true;
        }

        /**
         * Returns if the word is in the data structure. A word could contain the dot character '.'
         * to represent any one letter.
         */
        public boolean search(String word) {
            char[] chars = word.toCharArray();
            return search(chars, 0);
        }

        private boolean search(char[] chars, int start) {
            WordDictionary cur = this;
            for (int i = start; i < chars.length; ++i) {
                if (chars[i] == '.') {
                    for (int j = 0; j < 26; ++j) {
                        if (cur.next[j] != null && cur.next[j].search(chars, i + 1)) {
                            return true;
                        }
                    }
                    return false;
                } else {
                    int pos = chars[i] - 'a';
                    if (cur.next[pos] == null) {
                        return false;
                    }
                    cur = cur.next[pos];
                }
            }
            return cur.isEnd;
        }
    }
}
